#pragma once

#include <vector>
/**
 * Simple insertion sort
 */
template <typename Comparable>
void insertionSort(std::vector<Comparable> & a)
{
	int j;
	for (int p = 1; p < a.size(); p++)
	{
		Comparable tmp = a[p];
		for (j = p; j > 0 && tmp < a[j-1]; j--)
			a[j] = a[j-1];
		a[j] = tmp;
	}
}

template <typename Comparable>
void insertionSort(std::vector<Comparable> & a, int left, int right)
{
	int j;
	for (int p = left+1; p < right+1; p++)
	{
		Comparable tmp = a[p];
		for (j = p; j > 0 && tmp < a[j-1]; j--)
			a[j] = a[j-1];
		a[j] = tmp;
	}
}

/**
 * Shellsort, using Shell's (poor) increments.
 */
template <typename Comparable>
void shellSort(std::vector<Comparable> & a)
{
	for (int gap = a.size()/2; gap > 0; gap /=2)
		for (int i = gap; i < a.size(); i++)
		{
			Comparable tmp = a[i];
			int j = i;
			for (; j >= gap && tmp < a[j-gap]; j -= gap)
				a[j] = a[j-gap];
			a[j] = tmp;
		}
}

template <typename Comparable>
void heapSort(std::vector<Comparable> & a)
{
	for (int i = a.size() / 2; i >= 0; i--)
		percDown(a, i, a.size());
	for (int j = a.size() - 1; j > 0; j--)
	{
		swap(a[0], a[j]);
		percDown(a, 0, j);
	}
}

inline int leftChild(int i)
{
	return 2 * i + 1;
}

template <typename Comparable>
void percDown(std::vector<Comparable> & a, int i, int n)
{
	int child;
	Comparable tmp;
	
	for (tmp = a[i]; leftChild(i) < n; i = child)
	{
		child = leftChild(i);
		if (child != n -1 && a[child] < a[child + 1])
			child++;
		if (tmp < a[child])
			a[i] = a[child];
		else
			break;
	}
	a[i] = tmp;
}

template <typename Comparable>
void mergeSort(std::vector<Comparable> & a)
{
	std::vector<Comparable> tmpArray(a.size());
	mergeSort(a, tmpArray, 0, a.size() -1);
}

template <typename Comparable>
void mergeSort(std::vector<Comparable> & a,
			std::vector<Comparable> & tmpArray, int left, int right)
{
	if (left < right)
	{
		int center = (left + right) / 2;
		mergeSort(a, tmpArray, left, center);
		mergeSort(a, tmpArray, center + 1, right);
		merge(a, tmpArray, left, center + 1, right);
	}
}

template <typename Comparable>
void merge(std::vector<Comparable> & a, std::vector<Comparable> & tmpArray,
			int leftPos, int rightPos, int rightEnd)
{
	int leftEnd = rightPos -1;
	int tmpPos = leftPos;
	int numElements = rightEnd - leftPos +1;

	//Main loop
	while (leftPos <= leftEnd && rightPos <= rightEnd) {
		if (a[leftPos] <= a[rightPos])
			tmpArray[tmpPos++] = a[leftPos++];
		else
			tmpArray[tmpPos++] = a[rightPos++];
	}

	while (leftPos <= leftEnd)
		tmpArray[tmpPos++] = a[leftPos++];
	while (rightPos <= rightPos)
		tmpArray[tmpPos++] = a[rightPos++];

	// Copy tmpArray back
	for (int i = 0; i < numElements; i++, rightEnd--)
		a[rightEnd] = tmpArray[rightEnd];
}

/**
 * QuickSort algorithm (driver)
 */
template <typename Comparable>
void quickSort(std::vector<Comparable> & a)
{
	quickSort(a, 0, a.size() - 1);
}

/**
 * Return median of left, center, and right.
 * Order these and hide the pivot.
 */
template <typename Comparable>
const Comparable & median3(std::vector<Comparable> & a, int left, int right)
{
	int center = (left + right) /2;
	if (a[center] < a[left])
		swap(a[left], a[center]);
	if (a[right] < a[left])
		swap(a[left], a[right]);
	if (a[right] < a[center])
		swap(a[center], a[right]);

	swap(a[center], a[right -1]);
	return a[right-1];
}

/**
 * Internal quicksort method that makes recursive calls.
 * Uses median-of-three partitioning and a cutoff of 10.
 * a is an array of Comparable items.
 * left is the left-most index of the subarray.
 * right is the right-most index of the subarray.
 */
template <typename Comparable>
void quickSort(std::vector<Comparable> & a, int left, int right)
{
	if (left + 10 <= right)
	{
		Comparable pivot = median3(a, left, right);

		int i = left, j = right -1;
		for ( ; ; )
		{
			while (a[++i] < pivot) {}
			while (pivot < a[--j]) {}
			if (i < j)
				swap(a[i], a[j]);
			else
				break;
		}
		swap(a[i], a[right -1]);
		
		quickSort(a, left, i-1);
		quickSort(a, i+1, right);
	}
	else
		insertionSort(a, left, right);
}